#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;

class Solution
{
public:
	int minMutation(string startGene, string endGene, vector<string>& bank)
	{
		map<string, vector<string>> map;
		map[startGene] = {};
		for (const string& b : bank)
		{
			map[b] = {};
			for (auto pair : map)
			{
				if (pair.first == b)
					continue;
				int change = 0;
				for (int i = 0; i < 8; i++)
				{
					if (pair.first[i] != b[i])
					{
						change++;
						if (change > 1)
							break;
					}
				}
				if (change == 1)
				{
					map[b].push_back(pair.first);
					map[pair.first].push_back(b);
				}
			}
		}
		//search
		set<string> visited;
		queue<string> que;
		que.push(startGene);
		int level = 0;
		while (!que.empty())
		{
			int size = que.size();
			for (int i = 0; i < size; i++)
			{
				string cur = que.front();
				if (cur == endGene)
					return level;
				visited.insert(cur);
				for (auto c : map[cur])
				{
					if (visited.find(c) == visited.end())
					{
						que.push(c);
					}
				}
				que.pop();
			}
			level++;
		}
		return -1;
	}
};

int main()
{
	cout << "Code433" << endl;
	Solution s;
	string start = "AAAAACCC";
	string end = "AACCCCCC";
	vector<string> bank = { "AAAACCCC","AAACCCCC","AACCCCCC" };
	cout << s.minMutation(start, end, bank);
	return 0;
}